package com.bclz.datastructures

import java.util

import scala.annotation.tailrec


/**
  * Binary Heap: Mini-Max Heap
  * 这里举例采用得是Max Heap
  *
  * 利用最大二叉堆的dequeue，每次都是数最大的元素，可以实现优先队列
  */

class BinaryHeap() {

  var eles: Array[Int] = new Array(32)
  var size: Int = 0

  def this(e: Array[Int]) {
    this()
    eles = BinaryHeap.buildBinaryHeap(e)
    size=e.length
  }

  /**
    * 加入堆底，然后上浮
    *
    * @param value
    */
  def enqueue(value: Int): Unit = {

    if (size >= eles.size) {
      resize()
    }
    eles(size) = value
    size = size + 1
    upAdjust(size)
  }

  /**
    * 删除堆顶，堆低移到堆顶
    * 堆顶下沉
    *
    * @return
    */
  def dequeue(): Int = {
    val head = eles(0)
    eles(0) = eles(size - 1)
    size = size - 1
    downAdjust(0)
    return head
  }

  private def resize(): Unit = {
    val oldSize = eles.length
    val newSize = 2 * oldSize
    eles = util.Arrays.copyOf(eles, newSize)
  }

  private def downAdjust(i: Int): Unit = {
    val leftNodeIndex = 2 * i + 1
    val rightNodeIndex = 2 * i + 2
    if (leftNodeIndex >= size || rightNodeIndex >= size) {
      return
    }
    var maxIndex = leftNodeIndex;
    if (rightNodeIndex < size && eles(rightNodeIndex) > eles(leftNodeIndex)) {
      maxIndex = rightNodeIndex
    }
    val temp = eles(i)
    eles(i) = eles(maxIndex)
    eles(maxIndex) = temp
    downAdjust(i + 1)
  }

  private def upAdjust(i: Int): Unit = {
    val parentNodeIndex = if ((i & 1) == 0) (i - 2) / 2 else (i - 1) / 2
    if (parentNodeIndex < 0) return
    val temp = eles(i)
    if (temp > eles(parentNodeIndex)) {
      eles(i) = eles(parentNodeIndex)
      eles(parentNodeIndex) = temp
    }
    upAdjust(parentNodeIndex)
  }
}


object BinaryHeap {


  def apply(array: Array[Int]): Array[Int] = buildBinaryHeap(array)


  /**
    * current index i  ,左右节点 为(2i+1  ,2i+2)
    *
    * 2
    * 3   4
    * 1  7  8  7
    * 0
    *
    * 最后的一个无子节点   len=2i+2    i=(len-2)/2   i+1=len/2
    *
    *
    * 从最后一个无子节点len/2, 向上开始遍历(eg: 从7开始)
    *
    * 遍历总长度为len/2,每个节点最多遍历
    * log   (len+1)     次 ,共len log,(len+1)次
    * 2
    * 时间复杂度为为nlogn
    * 空间复杂度为1
    *
    * @param array
    * @return
    */
  private def buildBinaryHeap(array: Array[Int]): Array[Int] = {

    var currentIndex = array.length / 2

    while (currentIndex >= 0) {
      downAdjust(array, currentIndex)
      currentIndex -= 1
    }
    array
  }

  @tailrec
  def downAdjust(array: Array[Int], index: Int): Unit = {

    if (2 * index + 1 >= array.length) return;
    val currentVal = array(index)
    val leftNodeIndex = 2 * index + 1
    val leftVal = array(leftNodeIndex)
    val rightNodeIndex = 2 * index + 2
    val maxIndex = if (rightNodeIndex < array.length) {
      val rightVal = array(rightNodeIndex)
      (if (leftVal > rightVal) leftNodeIndex else rightNodeIndex)
    } else leftNodeIndex
    val maxVal = array(maxIndex)
    if (currentVal < maxVal) {
      array(index) = maxVal
      array(maxIndex) = currentVal

      downAdjust(array, maxIndex)
    }

  }

  /**
    * 堆顶元素不删除，与堆底元素交换
    * max-heap堆顶元素为最大元素，交换后堆底为最大元素，
    * 每次交换后，下沉堆顶元素(下沉长度len-1).多次交换后数组就是升序排列的数组了。
    *
    * 1.构建二叉堆nlogn
    * 2.顶低元素交换下沉nlogn
    *
    * 最坏  下沉一次logn,   时间复杂度为nlogn+nlogn
    *
    * @param array
    * @return
    */
  def sortByBinaryHeap(array: Array[Int]): Array[Int] = {

    val binaryHeap = buildBinaryHeap(array)
    var i = array.length - 1
    while (i >= 0) {
      val temp = array(0)
      array(0) = array(i)
      array(i) = temp
      downAdjust(binaryHeap, 0, i)
      i -= 1
    }

    return array

  }

  @tailrec
  def downAdjust(array: Array[Int], index: Int, searchLen: Int): Unit = {

    if (2 * index + 1 >= searchLen) return;
    val currentVal = array(index)
    val leftNodeIndex = 2 * index + 1
    val leftVal = array(leftNodeIndex)
    val rightNodeIndex = 2 * index + 2
    val maxIndex = if (rightNodeIndex < searchLen) {
      val rightVal = array(rightNodeIndex)
      (if (leftVal > rightVal) leftNodeIndex else rightNodeIndex)
    } else leftNodeIndex
    val maxVal = array(maxIndex)
    if (currentVal < maxVal) {
      array(index) = maxVal
      array(maxIndex) = currentVal
      downAdjust(array, maxIndex, searchLen)
    }

  }

  def main(args: Array[String]): Unit = {

    //    BinaryHeap(Array(2,1,5,4,3,6,3,7)).foreach(println(_))
//    BinaryHeap.sortByBinaryHeap(Array(2, 1, 5, 4, 3, 6, 3, 7, 44, 22, 55, 17, 23, 32232, 22, 11, 2, 8, 9)).foreach(println(_))
    val heap=new BinaryHeap(Array(2, 1, 5, 4, 3, 6, 3, 7, 44, 22, 55, 17, 23, 32232, 22, 11, 2, 8, 9))
    val i = heap.dequeue()
    val i2 = heap.dequeue()
    println("移除后堆大小:"+heap.size)
    println("移除的元素为:"+i+"+++++++"+i2)
  }


}
